package main

func main() {

	//root = [4,2,9,3,5,null,7]  深度3
	node3 := TreeNode{
		Val:   3,
		Left:  nil,
		Right: nil,
	}
	node4 := TreeNode{
		Val:   5,
		Left:  nil,
		Right: nil,
	}
	node5 := TreeNode{
		Val:   7,
		Left:  nil,
		Right: nil,
	}
	node1 := TreeNode{
		Val:   2,
		Left:  &node3,
		Right: &node4,
	}
	node2 := TreeNode{
		Val:   9,
		Left:  nil,
		Right: &node5,
	}
	root := TreeNode{
		Val:   4,
		Left:  &node1,
		Right: &node2,
	}

	//打印测试用例返回结果
	resp := minDepth(&root)
	println(resp)

}

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//二叉搜索树的插入实际上非常简单，不像二叉搜索树的删除那样
func insertIntoBST(root *TreeNode, val int) *TreeNode {
	//创建一个新结点
	node := TreeNode{
		Val:   val,
		Left:  nil,
		Right: nil,
	}
	//如果要插入的树是空树，那么直接返回该结点
	if root == nil {
		return &node
	}
	//工作指针
	workNode := root
	//找到要插入的位置
	for workNode != nil {
		//小于root，就找root的左子树
		if val < workNode.Val {
			if workNode.Left != nil { //判断左儿子是否为空，如果不为空就继续遍历，为空就插入到左儿子
				workNode = workNode.Left
			} else {
				workNode.Left = &node //找到并插入
				break
			}
		} else { //大于root，就找root的右子树
			if workNode.Right != nil { //判断右儿子是否为空，如果不为空就继续遍历，为空就插入到右儿子
				workNode = workNode.Right
			} else {
				workNode.Right = &node //找到并插入
				break
			}
		}
	}
	return root

}
